記錄學習內容。看網路上大大們的文章和影片，做些紀錄。
以下內容大多來自網路上大大們的文章。截圖也來自文章和影片。
還不了解，內容可能有錯誤。

6.2 Sum Of Subsets Problem – Backtracking

Subset Sum Problem | DP-25

How can one prove the knapsack problem is NP-complete?

輕鬆談演算法的複雜度分界：什麼是P, NP, NP-Complete, NP-Hard問題

給一個陣列
{3, 34, 4, 12, 5, 2}, sum = 9
如果裡面的數字挑選幾個出來，相加等於9
就代表符合這個問題。

像是

{3, 34, 4, 12, 5, 2}，sum = 30
因為沒有數字相加起來等於30的，所以這個問題的答案就是False

解法:

一次 選一個陣列裡的元素 出來 。
所以 左邊 代表 剩下幾個元素 ， 右邊代表 扣掉的數字 ，
像是 總和是9 ，就不斷挑選數字 ， 9 –數字-數字 ……
如果9 變成0 了，就代表 這些數字 相加 等於 9
這些數字 就是我們要的答案 。
然後 如果 從陣列挑選出來的數字 大於 9 – 數字 -數字 ……
，就代表現在裝不下 這個數字 ， 就會跳過這個數字。
像是現在選了3和4 ，所以9-3-4=2 ，不能再裝5了

所以第一種解法 ，就是一般的遞迴 ，要選這個數字，或是不選這個數字。

文章中有這段，Sum Of Subsets Problem是 NP-Complete問題

The problem is in-fact NP-Complete (There is no known polynomial time solution for this problem).

0-1 Knapsack Problem 跟 Subset Sum Problem，可以 互相證明是 NP-Complete 問題
(以下內容不確定。可能錯誤。)

在看一下 NP-Complete 問題 是什麼

只要滿足以下兩個條件的，我們都稱之為NP-Complete：
1.「問題」本身是一個NP問題
2.所有的NP問題都可以用DTM在 polynomial time 內化約成為這個「問題」。

不太懂

我們可以把0-1 Knapsack Problem在 polynomial time 內 降成 (reduce)Subset Sum Problem

現在背包 空間可以裝 50 kg -- > 當成 sum = 50

int val[] = new int[] { 60, 100, 120 }; -- > 物品價值
int wt[] = new int[] { 10, 20, 30 }; -- > 物品重量
物品重量或是物品價值 當成 數字陣列 { 10, 20, 30 }

選取的物品的總重量 不能超過 背包空間(50kg) 換成
選取的數字的總和 = 50

Subset Sum Problem 降成 (reduce) 0-1 Knapsack Problem

每個陣列裡的數字{3, 34, 4, 12, 5, 2} 當成 每個物品的重量、每個物品的$$

總數字總和(9) 當成 總重量

文章中這段的意思:
(reduce)後的 Knapsack problem 是正確的話，Subset-sum問題也會是正確的?
一邊正確，另一邊就正確。

The Yes/No answer to the new problem corresponds to the same answer to the original problem. You can check it easily that Yes instance of Subset-sum maps to Yes instance of Knapsack problem and vice-versa.

用來證明NP-complete的方法:
NP-complete在多項式時間內 換成 另一個NP-complete問題 。

A general strategy for this type of question is to show that another NP-complete type of problem could be transformed into this type of problem in polynomial time.

接著來看Subset Sum Problem動態規劃的方法:

boolean subset[][] = new boolean[sum + 1][n + 1];
subset[][] 就代表 : 該數字能不能 在 這個總和下 ，放到答案裡。
True 代表 能加到答案裡。

左邊的0、3、4、5、2代表 陣列裡的數字 。
最上面的橫排 代表總和是6 。

來看文章中的程式碼:

看不太懂 ，假如現在是subset [2][4] 。
subset [2][4] 會先等於 subset [2][3] ，
也就是2這個數字在 2 這個總和下 和 跟 前一個數字 在2 這個總和下，先同樣的狀況。

接著如果 i (總和數字，2) >= set [j-1] (目前指到的數字，2)
代表 現在還裝得下這個數字

|| 代表or運算(有一個是true 就是true)。

答案可能是 目前的答案 ， 或是 subset [i - set[j - 1]] [j - 1]

像是subset [2][4] 的狀況下 ， i是2，j是4，set[j-1] = set[3] = 2
i - set[j - 1] 就是 2 – 2 = 0。

subset [i - set[j - 1]][j - 1] 代表 subset[目前總和 扣掉 現在這個數字 ][ 前一個數字 ]
--- > 如果是T ，代表可以裝這個數字

不知道有沒有錯誤，總之非常不懂，
[2][4] 先等於 [2][3] 的狀況
然後因為 背包還裝得下這個數字，所以
要去找 前一個數字下， 扣掉這個數字的背包 ，的狀況是不是T 。
這邊是[0][3] 所以是True

可能理解有錯誤，總之先到這。

教學中是採用回溯法（英語：backtracking）
https://zh.wikipedia.org/wiki/%E5%9B%9E%E6%BA%AF%E6%B3%95

不太了解，就是說 有些狀況，是不行的，就取消。
參考:
【演算法】資工人必下的一盤棋－八皇后 Eight Queens
https://www.youtube.com/watch?v=kyLxTdsT8ws&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=65&ab_channel=AbdulBari